﻿// poj3111 K Best.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;
/*

http://poj.org/problem?id=3111

K 最佳
时间限制：8000MS 内存限制：65536K
总提交量。20215 已接受。4903
案件时间限制：2000MS 特别法官
案件描述

德米有N件珠宝。她的每件珠宝都有一定的价值vi和重量wi。
图片
由于她的丈夫约翰在最近的金融危机中破产，黛米决定出售一些珠宝。她决定为自己保留K个最好的珠宝。她决定保留这样的珠宝，使其具体价值越大越好。
也就是说，将一组珠宝S={i1, i2, ..., ik}的具体价值表示为

.

德米想选择这样的k个珠宝，使其具体价值尽可能大。请帮助她做到这一点。

输入文件

输入文件的第一行包含n--Demy得到的珠宝数量，以及k--她想保留的珠宝数量（1≤k≤n≤100 000）。

接下来的n行包含两个整数--vi和wi（0≤vi≤106，1≤wi≤106，所有vi和所有wi的总和都不超过107）。

输出

输出k个数字--Demy必须保留的珠宝数量。如果有多个解决方案，则输出任何一个。

输入样本

3 2
1 1
1 2
1 3
样本输出

1 2
*/

const int N = 100010;
struct JEW {
    int val, weight, id;
}jews[N];
int n, k;

pair<double, int> res[N];


bool check(double m) {
    for (int i = 0; i < N; i++) {
        res[i].first = 0; res[i].second = 0;
    }

    for (int i = 0; i < n; i++) {
        res[i].first = jews[i].val - m * jews[i].weight;
        res[i].second = jews[i].id;
    }

    sort(res, res + n);
    double sum = 0.0;
    for (int i = n - 1; i > n - 1 - k; i--) {
        sum += res[i].first;
    }

    if (sum > 1e-7) { return false; }
    return true;
}

int main()
{
    //cin >> n >> k;
    scanf("%d%d",&n,&k);
    for (int i = 0; i < n; i++) {
        //cin >> jews[i].val >> jews[i].weight;
        scanf("%d%d",&jews[i].val,&jews[i].weight);
        jews[i].id = i;
    }

    double l = 0; double r = 1000001;
    while (r - l > 1e-7) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        }
        else {
            l = mid;
        }
    }

    for (int i = n - 1; i > n - 1 - k; i--) {
        printf("%d ", res[i].second + 1);
        //cout << res[i].second+1 << " ";
    }

    return 0;
}

 